package popcount

// pc[i] is the population count of i.
var pc [256]byte

func init() {
	for i := range pc {
		pc[i] = pc[i/2] + byte(i&1)
	}
}

// PopCount returns the population count (number of set bits) of x
func PopCount(x uint64) int {
	return int(pc[byte(x>>(0*8))] +
		pc[byte(x>>(1*8))] +
		pc[byte(x>>(2*8))] +
		pc[byte(x>>(3*8))] +
		pc[byte(x>>(4*8))] +
		pc[byte(x>>(5*8))] +
		pc[byte(x>>(6*8))] +
		pc[byte(x>>(7*8))])
}

// 练习2.3 用一个循环代替单一的表达式
func PopCount1(x uint64) int {
	var bits = 0
	var i uint64
	for i = 1; i <= x; i *= 2 {
		if (x == x|i) {
			bits++
		}
	}
	return bits
}

// 练习 2.4: 用移位算法重写PopCount函数，每次测试最右边的1bit，然后统计总数。比较和查表算法的性能差异。
func PopCount2(x uint64) int {
	var bits = 0
	for x != 0 {
		if (x % 2 == 1) {
			bits++
		}
		x = x>>1
	}
	return bits
}

// 练习 2.5: 表达式 x&(x-1) 用于将x的最低的一个非零的bit位清零。使用这个算法重写 PopCount函数，然后比较性能
func PopCount3(x uint64) int {
	var bits = 0
	for x != 0 {
		x &= (x-1)
		bits++
	}
	return bits
}